use std::ptr;

struct TreeNode {
    element: i32,
    left: *mut TreeNode,
    right: *mut TreeNode,
}

impl TreeNode {
    fn new(element: i32) -> Self {
        TreeNode {
            element,
            left: ptr::null_mut(),
            right: ptr::null_mut(),
        }
    }
}

type SearchTree = *mut TreeNode;
type Position = *mut TreeNode;

fn make_empty(t: SearchTree) -> SearchTree {
    unsafe {
        if !t.is_null() {
            make_empty((*t).left);
            make_empty((*t).right);
            let _ = Box::from_raw(t); // Deallocate memory
        }
    }
    ptr::null_mut()
}

fn find(x: i32, mut t: SearchTree) -> Position {
    unsafe {
        while !t.is_null() {
            if x < (*t).element {
                t = (*t).left;
            } else if x > (*t).element {
                t = (*t).right;
            } else {
                return t; // Match found
            }
        }
    }
    ptr::null_mut() // No match
}

fn find_min(mut t: SearchTree) -> Position {
    unsafe {
        while !(*t).left.is_null() {
            t = (*t).left;
        }
    }
    t
}

fn find_max(mut t: SearchTree) -> Position {
    unsafe {
        while !(*t).right.is_null() {
            t = (*t).right;
        }
    }
    t
}

fn insert(x: i32, t: SearchTree) -> SearchTree {
    unsafe {
        if t.is_null() {
            let new_node = Box::new(TreeNode::new(x));
            Box::into_raw(new_node)
        } else {
            if x < (*t).element {
                (*t).left = insert(x, (*t).left);
            } else if x > (*t).element {
                (*t).right = insert(x, (*t).right);
            }
            t
        }
    }
}

fn delete(x: i32, t: SearchTree) -> SearchTree {
    unsafe {
        if t.is_null() {
            panic!("Element not found");
        } else {
            if x < (*t).element {
                (*t).left = delete(x, (*t).left);
            } else if x > (*t).element {
                (*t).right = delete(x, (*t).right);
            } else if !(*t).left.is_null() && !(*t).right.is_null() { // Two children
                let tmp_cell = find_min((*t).right);
                (*t).element = (*tmp_cell).element;
                (*t).right = delete((*t).element, (*t).right);
            } else { // One or zero children
                let old_node = if (*t).left.is_null() { (*t).right } else { (*t).left };
                let _ = Box::from_raw(t);
                return old_node;
            }
        }
        t
    }
}

fn retrieve(p: Position) -> i32 {
    unsafe { (*p).element }
}

fn main() {
    let mut tree: SearchTree = make_empty(ptr::null_mut());

    for i in 0..50 {
        let j = (i + 7) % 50;
        tree = insert(j, tree);
    }

    for i in 0..50 {
        let p = find(i, tree);
        if p.is_null() || retrieve(p) != i {
            println!("Error at {}", i);
        }
    }

    for i in (0..50).step_by(2) {
        tree = delete(i, tree);
    }

    for i in (1..50).step_by(2) {
        let p = find(i, tree);
        if p.is_null() || retrieve(p) != i {
            println!("Error at {}", i);
        }
    }

    for i in (0..50).step_by(2) {
        let p = find(i, tree);
        if !p.is_null() {
            println!("Error at {}", i);
        }
    }

    let min = retrieve(find_min(tree));
    let max = retrieve(find_max(tree));
    println!("Min is {}, Max is {}", min, max);
}
